package com.zjj.algorithm.learning.leetcode.str;

import java.util.ArrayList;
import java.util.List;

/**
 * 6. Z 字形变换 中档题
 * <p>
 * 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
 * <p>
 * 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
 * <p>
 * P   A   H   N
 * A P L S I I G
 * Y   I   R
 * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
 * <p>
 * 请你实现这个将字符串进行指定行数变换的函数：
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "PAYPALISHIRING", numRows = 3
 * 输出："PAHNAPLSIIGYIR"
 * 示例 2：
 * 输入：s = "PAYPALISHIRING", numRows = 4
 * 输出："PINALSIGYAHRPI"
 * 解释：
 * P     I    N
 * A   L S  I G
 * Y A   H R
 * P     I
 * 示例 3：
 * <p>
 * 输入：s = "A", numRows = 1
 * 输出："A"
 *
 * @author zjj_admin
 * @date 2022/11/24 9:43
 */
public class ZigzagConversion {

    public static void main(String[] args) {
        String s = "PAYPALISHIRING";
        String s1 = "enrxihcsanbtgxdcttnujvfscrwqtyuynmxwvbqxorquowzhpmdzjlrlcncyoywbmvzhxpenhvivthfivkhfxbqaquyetwifthnsxrggoqbhxiqsvzzscqutmszfqjnmtaeqtmykcbrzkjuhltznluiyokfhvstouzgqmeaogrqsdmzohydtuotjyysttlknmqdyvdpbxftatuqastvphoahpsdifnxrfbqaghdfoyhhsxhntdcctcmiupqzeqsjrkmzrphfoooioyvjdxnwbzhvqzwuprgibsitjpazfritpfesfsqgrxekxcgmtmvvgfqqwspdjxzaddukvlqpkuzjzhwsutpcafsyaibjhammegwbtpqelrnkbldxguzgcseccinlizyogwqzlifxcthdgmanjztltanviajschhkdxlrfrohmxmsmmhvodihdvfnxofbxmlclxvrojacjpwxbeurhcbmzgzwwgyvtlzeivxygaappzosdikkmlwltxirdioytnfeieepehgvgvqjfavsntfiqnbvxputczznfdcmkkhshxdnzyhormwjcxfbobwrcvehbitnsdgacjpeiysbmrnoqssfvoyxkeglmaygfgihqznazgdmzqcpiuudjucvyjimlivqpdzhfnhevksudvjlrgrcavxzehlrqgjhmjqtyzztjsnopyagetjfqiexqroiayrojhjhgiarcpgrniysdhztpfqhwhpyfioopxxvgxniovabdatgjszazsiwzzweiluxirvqqkzefbhiddqmxrmxjwtiwrogckdldadtkczpfhzikpujhjgqfbbbt";
        long start = System.currentTimeMillis();
        String res = convert2(s, 4);
        long end = System.currentTimeMillis();
        System.out.println("(end-start) = " + (end - start));
        System.out.println("res = " + res);

    }


    /**
     * 时间
     * 37 ms
     * 击败
     * 14.54%
     * 内存
     * 42.8 MB
     * 击败
     * 18.87%
     * <p>
     * 思路：借助与二维数组
     * 1、将数据存储到相应的二维数组中
     * 2、二维数组的行数为题目给出的 numRows，关键需要计算出二维数组的列
     * 3、设第一列全部到第二列全部（不包括第二列）之间的个数为 x，则 x = numRows + (numRows - 2) = 2 * numRows - 2
     * 4、设 第一列全部到第二列全部（不包括第二列） 为一组 用 n 表示，那么 [2 * numRows - 2] * n >= s 的长度
     * 5、其中 一个 n 的大小为 x - 1
     * 6、这样就可以计算出 x、n，进一步给出数组的列
     *
     * @param s
     * @param numRows
     * @return
     */
    public static String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        int len = s.length();
        //计算出有多少组，最后若有余数就需要多一组
        int n = 0;
        if (len % (2 * numRows - 2) == 0) {
            n = len / (2 * numRows - 2);
        } else {
            n = len / (2 * numRows - 2) + 1;
        }
        //得出二维数组的列
        int numCols = n * (numRows - 1);
        //创建二维数组
        char[][] temp = new char[numRows][numCols];
        //将数据存按照规则存放到 temp 数组中
        char[] chars = s.toCharArray();
        int index = 0;
        int r = 0;
        //一列一列的添加数据
        for (int c = 0; c < numCols; c++) {
            //当将字符串中的数据取完之后，直接退出即可
            if (index >= chars.length) {
                break;
            }
            if (r == 0) {
                while (r < numRows) {
                    //行数
                    temp[r][c] = chars[index];
                    // chars 索引后移
                    index++;
                    //当将字符串中的数据取完之后，直接退出即可
                    if (index >= chars.length) {
                        break;
                    }
                    r++;
                }
                continue;
            }

            //当 r 不为 0 时
            if (r == numRows) {
                r -= 2;
            } else {
                r--;
            }
            //当 r == 0 时，说明此时填充了数组的第二行，让列的数据 - 1
            if (r == 0) {
                c--;
                continue;
            }
            temp[r][c] = chars[index++];
        }

        StringBuilder res = new StringBuilder();
        for (int i = 0; i < temp.length; i++) {
            for (int j = 0; j < temp[i].length; j++) {
                System.out.print(temp[i][j] + " ");
                if (temp[i][j] != '\u0000') {
                    res.append(temp[i][j]);
                }
            }
            System.out.println();
        }
        return res.toString();
    }


    /**
     *
     * @param s
     * @param numRows
     * @return
     */
    public static String convert2(String s, int numRows) {
        if(numRows < 2) {
            return s;
        }
        List<StringBuilder> rows = new ArrayList<>();
        for(int i = 0; i < numRows; i++) {
            rows.add(new StringBuilder());
        }
        int i = 0, flag = -1;
        for(char c : s.toCharArray()) {
            rows.get(i).append(c);
            if(i == 0 || i == numRows -1) {
                flag = - flag;
            }
            i += flag;
        }
        StringBuilder res = new StringBuilder();
        for(StringBuilder row : rows) {
            res.append(row);
        }
        return res.toString();
    }
}
